00100				COMPUTER VISION
00200	    				  
00300			 Thomas O. Binford, Stanford University 
00400					and
00500			Jay M. Tenenbaum, Stanford Research Institute
00600	
00700	
00800				Introduction
00900	
01000	"Intelligent" computers require knowledge of their  environment,  and
01100	the  most  effective  means of acquiring such knowledge is by seeing.
01200	Vision opens a new realm of computer applications.  Weather  analysis
01300	from  cloud  maps  and  medical  diagnosis from x-rays and blood cell
01400	counts are two of many high volume data processing tasks that require
01500	pictorial  input.  Man-machine communication will be facilitated if a
01600	person can directly show the computer  a  real  object,  rather  than
01700	describe  it symbolically.  Designers, for example, could then easily
01800	obtain a computerized structural analysis of scale models.
01900	
02000	A particularly exciting area of application is industrial automation.
02100	Today  in  industry  there are hundreds of machines called industrial
02200	robots.   These programmable manipulators can repetitively execute  a
02300	precise  sequence of motions, but have no sensors and are thus unable
02400	to react dynamically  to  contingencies.      Simple  sensors  and  a
02500	minicomputer   could,   at   slight   additional   cost,  turn  these
02600	manipulators into true robots. With primitive visual  skills,machines
02700	could align mating parts in assembly operations, increase reliability
02800	by self-calibration, detect flaws, and avoid disasters.   Vision will
02900	also  minimize  the  present need for precise positioning of parts at
03000	each work station; parts could instead be transported in  a  bin  and
03100	picked out as needed.
03200	
03300	The  study  of  perception also provides valuable insights into human
03400	and machine information processing. Many of the problems  encountered
03500	are   fundamental  to  intelligent  activity.  For  example,  how  is
03600	knowledge represented?     How does  knowledge  provide  guidance  in
03700	drawing  conclusions  from  perceptual  data?     How  does  existing
03800	knowledge interact with conclusions drawn from an  image  to  acheive
03900	learning?   Questions  that  arise  in  the  implementation of vision
04000	systems have broad relevance to  computer  science:    How  shoulc  a
04100	complex  task  be  partitioned  into modules?  How should the modules
04200	communicate to share their knowledge and special capabilities?    How
04300	should  systems  with  highly interdependent modules be structured to
04400	facilitate modification?
04500	
04600	Techniques developed for machine perception cannot be taken literally
04700	as  models  for biological systems because of differences in hardware
04800	and gaps in our knowledge.    However,  fundamental  limitations  are
04900	shared, suggesting that some of the principles might also be found in
05000	nature.   Computer vision research may, in turn, occasionally  borrow
05100	from biology, but we cannot copy nature, since again, the details are
05200	not yet known and the hardware is different.
05300	
05400	
05500	Historically,   computer   vision  emerged  from  the  study  of  two
05600	dimensional pattern recognition.  However, it is seldom  possible  to
05700	apply the mathematical formalisms developed for classification to the
05800	analysis of real scenes.   Consider the visual  requirements  for  an
05900	organism  such  as  a robot. It must manipulate or avoid objects, not
06000	just classify them.         Manipulation  requires  three-dimensional
06100	interpretations  and  spatial relations of objects.  In problems such
06200	as character recognition, it was attractive to simply save images  or
06300	feature vectors, and then match against an image or part of an image.
06400	But in real scenes, objects occlude one another, they have parts with
06500	joints that move separately, there are many viewpoints, many possible
06600	objects, and many combinations of objects. Object classes,  moreover,
06700	are  often  defined by function, not shape (e.g., the class of coffee
06800	cups).     Direct template matching techniques  are  impractical  for
06900	these requirements, except in very carefully controlled applications.
07000	Perception involves complex deductions  in  order  to  understand  an
07100	image in terms of a priori knowledge of the world.
07200			ELEMENTS OF A VISUAL SYSTEM
07300	
07400	The computer eye is usually some form of TV camera with color filters
07500	and  a  turret  or  zoom  lens  for  closeup views.      The computer
07600	controls filters, lens and other parameters to optimize the image for
07700	each  task [1].   A recent study has suggested alternative sensors to
07800	overcome the inadequate dynamic  range  of  television  systems  [2].
07900	Range  information  greatly  simplifies the interpretation of scenes.
08000	Humans use depth information obtained from stereo and  a  variety  of
08100	inferred  cues such as motion parallax and the size of known objects.
08200	Since these techniques require subtantial processing,  it  is  easier
08300	for  machines  to obtain depth by direct measurement.   Several depth
08400	sensors based on triangulation have been built [3, 4].
08500	
08600	A TV image is read into memory  as  an  array  of  brightness  values
08700	(typically  300x300) with 4 to 8 bits for each sample for each color.
08800	Computer vision can be thought of as the process of transforming this
08900	mass  of numbers into a symbolic description. The translation process
09000	can   be   subdivided   into   segmentation,   representation,    and
09100	interpretation.
09200	
09300	The  process  of  segmentation  partitions  a  scene  into meaningful
09400	entities that may be  recognizable.       Segmentation  in  character
09500	recognition   is  simple,  since  printed  characters  are  spatially
09600	separated and have high contrast with white paper. It  is  harder  to
09700	segment  objects  in  a real scene (even simple scenes) since objects
09800	may overlap  and  will  not  usually  be  separable  from  the  local
09900	background by a single attribute like brightness contrast.   Instead,
10000	segmentation must proceed by seeking regions of  uniform  brightness,
10100	color,  or  texture  (itself  a  complex descriptor), or regions with
10200	regular boundaries.   Segmentation may also depend on inferred  depth
10300	cues (e.g., texture gradients or suspected occlusion).
10400	
10500	In what form can we represent objects internally in the computer? The
10600	simplest form is a pictorial template, an array of brightness  values
10700	to  be  matched  directly against fragments of scenes by correlation.
10800	Given the inadequacies  of  this  representation,  we  must  describe
10900	partitioned  regions symbolically in terms of extracted features such
11000	as color, size,  texture,  and  shape.    These  properties  must  be
11100	inferred from the image by complex processes.  Simple descriptors for
11200	shape or texture may be used in simple  tasks  and  limited  context.
11300	Shape might be described by the ratio of the squared perimeter to the
11400	area of a region.  More sophisticated shape  representations,  needed
11500	for a wider range of tasks, are described later.
11600	
11700	Interpretation  is  often  expressed  as computing a distance measure
11800	between an object and a stored model.  For simple cases that approach
11900	can be useful.     When objects are occluded, there must be a partial
12000	match. When objects are not identical, judgments of similarity depend
12100	on  representation  of shape and representation of the task, in order
12200	to define important differences.   The most  useful  approach  is  to
12300	build  up  symbolic  descriptions  and  make symbolic descriptions of
12400	differences.     Sometimes there are  sufficiently  few  models  that
12500	matching  with  each  model is possible. More generally, the observed
12600	features must first be used to retrieve likely models  from  a  large
12700	visual memory.
12800	
12900	The integration of segmentation, representation and interpretation to
13000	achieve perception is illustrated by a system built at the University
13100	of  Edinburgh  [5] that can recognize a small set of ordinary objects
13200	such as pencils, eyeglasses  and  teacups.    Objects  are  presented
13300	against  a  contrasting  background.    Segmentation  is  achieved by
13400	partitioning the scene into regions of  uniform  brightness.  Objects
13500	are  represented  by  relational  graphs  detailing  gross attributes
13600	(e.g., size and  shape)  of  their  principal  regions  and  pairwise
13700	constraints   between  these  regions  (e.g.,  above,  larger  than).
13800	Interpretation  is  accomplished  by  mapping  the  relational  graph
13900	descriptions  of  known  objects  onto the segmented regions obtained
14000	from the scene, and seeking the best match.
14100	
14200	Experience with early bottom-up systems  of  this  type  led  to  the
14300	realization  that  the  three  basic processes of a perceptual system
14400	were highly interdependent; one cannot proceed  sequentially  through
14500	segmentation, representation, and interpretation and expect to obtain
14600	a globally consistent interpretation for all objects in a scene.  One
14700	problem  is  that  no  reliable  basis  exists for judging the global
14800	significance  of  segmentation  boundaries  using  local   similarity
14900	criteria.   Segmentation  must  be guided by interpretation to choose
15000	among many alternative partitionings, the alternative that leads to a
15100	globally  consistent and reasonable description of the scene.  A nice
15200	exposition of these ideas is given by Minsky [6].
15300	
15400				BLOCKS WORLD
15500	
15600	To avoid some of these difficulties, research concentrated  initially
15700	on  scenes  of  toy  blocks.   Roberts' [7] important work opened the
15800	field.   Objects were represented as  built  up  of  three  primitive
15900	parts,  a  block, a wedge, and a hexagonal prism. The program assumed
16000	that it would first obtain  perfect  line  drawings.   Interpretation
16100	meant   choosing   a  stored  three-dimensional  model  which,  after
16200	translation, rotation, and scaling, could be projected to match  part
16300	of  the  image.   The  recognized  piece  was  then  cut away and the
16400	remainder considered.  Primitives were represented by their  vertices
16500	in  three  dimensions. To decide on likely image points that belonged
16600	to a single  body,  the  program  attempted  to  identify  unobscured
16700	polygons,  and  then  match sets of vertices to topologically similar
16800	model vertices.  Line drawings were formed by  a  sequence  of  local
16900	operations.   Candidate  edge  points were considered by thresholding
17000	the gradient of intensity.   Isolated  edge  points  were  discarded.
17100	Connected  line  fragments  were  concatenated  into  lines that were
17200	segmented at corners by a sequential least squares line fit.  Merging
17300	of collinear lines bridged some gaps.
17400	
17500	That  system  organization has proven inadequate. It is not enough to
17600	use models and template matching. Producing perfect line drawings  is
17700	not  practical.     Some  lines  are missed; shadows, reflections and
17800	surface markings cause extra lines; errors  made  at  one  stage  are
17900	compounded  by later stages.  These deficiencies motivated subsequent
18000	research.
18100	
18200	Guzman [8] found it possible to segment complex scenes  into  objects
18300	without template matching, by observing that some vertices give local
18400	evidence that adjacent regions belong to the same body. In Figure  1,
18500	vertices A,B,C,E,G,H and I give evidence that adjacent regions belong
18600	to the same body, while vertex F does not.  Vertex D, which resembles
18700	G,  gives  misleading  evidence.     To  avoid such coincidences, the
18800	program required confirmation.      Regions linked twice were  joined
18900	into  clusters;  regions  linked twice to a cluster were also joined.
19000	Regions linked only to a single cluster  were  also  joined  to  that
19100	cluster.   Eventually  the  program  evolved  to  include inhibitions
19200	against certain links by requiring similar conditions at both ends of
19300	a line.  Other links were introduced without much motivation.
19400	
19500	This  program  was an important advance.    Bodies could be segmented
19600	without recognition and without explicit models.    The  program  did
19700	surprisingly   well,   but   had   problems   with  holes  and  other
19800	non-convexities, and with accidental  alignment.     being  told  the
19900	background.     Guzman  also  could not cope well with imperfect line
20000	drawings. For example, in the case of Figure 2 his program would fail
20100	because  a  missing line makes region R3 common to both the block and
20200	wedge.  Falk [9] was able to avoid some of the errors associated with
20300	missing  boundaries  by using an approach resembling Guzman's to link
20400	line segments likely to belong to the same object instead of regions.
20500	
20600	The limited generality of both these programs was  due  to  the  fact
20700	that  they  were implemented as a collection of ad hoc heuristics for
20800	segmentation with no explicit understanding of line drawings.   Thus,
20900	while  Falk himself realized that regions like R3 were non-planer and
21000	could not arise in a scene  containing  only  trihedral  solids,  his
21100	program  could not reason at this level. Huffman [10] and Clowes [11]
21200	made theoretical analyses of objects  with  only  trihedral  vertices
21300	(three  planes at each vertex).  Using these analyses, edges could be
21400	classified at each vertex as  convex,  concave  and  obscuring.  Some
21500	drawings could then be rejected as impossible if a given line was not
21600	consistently labeled at each end. Waltz [12] expanded  that  labeling
21700	of lines to include cracks and whether adjacent regions were shadowed
21800	or illuminated. Since each vertex could have many interpretations. it
21900	would   seem   that  a  search  for  consistent  labelings  would  be
22000	unmanageable.      Instead, the increased precision  of  descriptions
22100	allows  rapid  discarding of wrong interpretations.      Not only are
22200	solutions possible, they are quickly obtained. Instead of a  complete
22300	tree  search,  it  was  adequate  to  consider  vertices in sequence,
22400	eliminating inconsistent  interpretations  as  each  new  vertex  was
22500	added.     This  produced  all  possible  interpretations of a scene.
22600	However,  other  criteria  can  then  be  used  to  choose  the  most
22700	reasonable  interpretation.     A detailed survey of the work through
22800	Huffman appears in a recent text by Duda and Hart [13].
22900	
23000	
23100	
23200	
23300	
23400	The best performance in  extracting  line  drawings  from  television
23500	images  of polyhedra is given by the Shirai [14] and the Binford-Horn
23600	[15] line finders.   Shirai's system performs  better,  but  requires
23700	large contrast between objects and background (e.g., white on black),
23800	and finds only features and objects for which cues are available from
23900	context.      The Binford-Horn system is able to find most lines in a
24000	scene of white blocks on a white background in arbitrary lighting. It
24100	misses  a  few  lines,  which can usually be inferred from those that
24200	were  found,  and  garbles  some  vertices.   The  two  systems   are
24300	complementary and should be combined.
24400	
24500	The two programs are based on different principles.  Shirai's program
24600	first found the outer boundaries of an object or cluster of  objects.
24700	It   then  tried  to  guess  additional  lines  that  were  parallel,
24800	perpendicular, or extensions to lines already  found.     Search  for
24900	missing lines concentrated around vertices in the preliminary drawing
25000	where they would be most likely found. The use  of  context  involved
25100	not  changing  thresholds, but using special-purpose operators--e.g.,
25200	verify a line at known position and angle;  find  a  line  through  a
25300	vertex.   Figure  3  illustrates  the complexity of scenes handled by
25400	Shirai's program. The Binford-Horn system was intended to provide the
25500	base  for  a  system  such  as  Shirai's  by providing a partial line
25600	drawing without special assumptions about the scene.  It used a local
25700	directional  edge operator and an optimal sequential decision process
25800	to group the edge points into continuous curves.
25900	
26000	It is interesting to compare these systems with biological ones.  The
26100	directional  edge  operators  [16], which are scanned over the image,
26200	are analogous to the edge-detector cells  discovered  by  Heubel  and
26300	Wiesel[17]  in  higher  animals.       In  practice, large brightness
26400	gradients at reflections and  on  curved  surfaces  cause  masses  of
26500	spurious  edge  fragments.       Smooth  gradients  are eliminated by
26600	subtracting the local average at each point,  a  process  similar  to
26700	lateral inhibition in the retina of animals.
26800	
26900	
27000	
27100				REAL-WORLD VISION
27200	
27300	
27400	
27500	The   blocks   world   illustrates  many  basic  aspects  of  machine
27600	perception.   However, since many critical  problems  encountered  in
27700	perceiving real-world scenes do not arise in the blocks world, few of
27800	the techniques  developed  extend  to  the  real-world  domain.   For
27900	example:
28000	
28100	(1)  The  region-growing  and  edge-finding  techniques developed for
28200	uniformly painted blocks cannot cope with the textures and variations
28300	of brightness that predominate in the real world.
28400	
28500	(2)  The  precise  topological descriptions that characterized simple
28600	polyhedra are inappropriate or unobtainable for  complex  real  world
28700	objects such as trees.
28800	
28900	(3)  Interpretation  by  exhaustively  matching  all known prototypes
29000	against each segmented body is not feasible  with  large  numbers  of
29100	objects and cluttered scenes.
29200	
29300	Description  of  simple  polyhedral scenes was difficult enough; with
29400	these added obstacles, is there hope for success  in  perceiving  the
29500	real  world?      Perception  in  the  blocks world sought a complete
29600	description of everything present. It may not be  possible  (or  even
29700	meaningful)   to  obtain  exhaustive  descriptions  of  real  scenes.
29800	However,  complete  descriptions  are  seldom  needed;  a  system  is
29900	typically  concerned  with  only a few objects required to complete a
30000	specific task.
30100	
30200	For blocks, we restricted our programs to black and white images  and
30300	distinguished structures of blocks solely on the basis of shape.   In
30400	the real world, there is a tremendous redundancy of visual cues.   We
30500	can use color, texture, depth, size, and surface orientation, as well
30600	as  shape,  whichever  distinguishes   a   particular   object   most
30700	effectively.
30800	
30900	Real-world  objects are usually found in well defined contexts--e.g.,
31000	telephones  are  expected  on  tables  but  not  in  waste   baskets.
31100	Recognition  of  a  few  prominent  landmarks, combined with a priori
31200	knowledge of the environment can thus severely restrict what  objects
31300	may  be present in each part of the scene. While these objects may be
31400	difficult  to  describe,  there  will  usually  be  sufficient   cues
31500	available  to  discriminate  easily among the alternatives.    Often,
31600	very gross descriptions of complex  attributes  such  as  shape  will
31700	suffice  to  discriminate among a limited number of grossly different
31800	alternatives (e.g., a person can be distinguished from a  dog  simply
31900	by the predominantly vertical orientation of a human body).
32000	
32100	Real-world  vision can be viewed as a strategy problem: Given a task,
32200	first decide where to look for objects of interest  and  then  decide
32300	how  to  distinguish  them  from  other  objects  that  might also be
32400	present.   The system must limit interpretations to a small subset of
32500	possible  objects, selected on the basis of a priori expectations and
32600	crude descriptions of the scene.     Segmentation  can  be  based  on
32700	attributes  that  are known to be uniform over these objects. The key
32800	problems of information overload are overcome by tightly coordinating
32900	segmentation  and interpretation with world knowledge and task goals.
33000	The overload problem cannot  be  solved  by  merely  building  faster
33100	computers   and  bigger  memories;  hardware  improvements  will  aid
33200	adequate techniques but do little for exhaustive techniques.
33300	
33400	The principal work to date on real world vision has  concentrated  on
33500	segmentation and representation.  Segmentation of textured scenes has
33600	been studies as a two-dimensional problem for agricultural and  earth
33700	resource  survey  applications.    Bajcsy  [18]  has analyzed outdoor
33800	scenes with perspective, where three-dimensional texture descriptions
33900	are  important.       Textures were described hierarchically in terms
34000	of  simpler  texture  elements  and  their   spatial   relationships.
34100	Descriptors  for  texture  elements  and  relations were derived from
34200	Fourier analysis.   Typical attributes were directionality (if  any),
34300	size,  contrast,  and  spacing  of texture elements.      The Fourier
34400	transform was found troublesome,however, and color  descriptors  were
34500	added to improve performance.  Some depth relations could be observed
34600	from texture gradient.     An attempt was made to  obtain  consistent
34700	interpretations  by first confirming region boundaries by independent
34800	properties, making three-dimensional  interpretations,  and  matching
34900	region  descriptors with those of sky, trees, grass, etc.  in a world
35000	model.
35100	
35200	The  quality  of  interpretation  was  limited  by  unreliability  of
35300	region-growing  processes. Further work in outdoor scenes attempts to
35400	incorporate the  world  model  and  interpretation  into  the  region
35500	growing process. Regions are merged not only because of similarity of
35600	properties, but because the consistency of semantic interpretation is
35700	improved.
35800	
35900	
36000	Typical  robot  tasks  such  as  manipulation,  collision  avoidance,
36100	display,  and  recognition  were  analyzed to determine computational
36200	primitives required for descriptions of shape.  Although  some  would
36300	disagree, our criteria for shape representation are [19]:
36400	
36500	(1)  Representations  should  be symbolic at a high level in order to
36600	interface with knowledge of the problem domain.
36700	
36800	(2) Representations should depend on segmentation into  parts,  which
36900	may have sub-parts.
37000	
37100	(3)  Primitives  should  be  three-dimensional  volume  descriptions,
37200	rather than surface descriptions, to allow a natural choice of parts.
37300	
37400	(4) Descriptions should be generative.      A  modest  collection  of
37500	primitives should allow description of a vast set of objects.
37600	
37700	We  will outline one representation that fulfils these desiderata for
37800	a large class of curved objects. Objects are described  in  terms  of
37900	components  that  are  simple  to  describe, and the relationships of
38000	these parts.  A useful shape primitive for many curved objects is  an
38100	arbitrary  space  curve,  and  normal  cross-sections along this axis
38200	(Figure 4).      Snake-like objects, helices,  toroids,  and  locally
38300	helical  and  toroidal shapes are naturally described [19]. Our basic
38400	definition of a simple piece is that the direction  of  its  axis  be
38500	continuous  and  that  the  cross-section function along that axis be
38600	continuous.    We look for large changes in  the  cross-section,  and
38700	consider  them  as  likely  places for segmenting the object.     The
38800	segmentation  process  must  be  flexible  and   able   to   generate
38900	alternative  propositions.     A higher-level routine will ultimately
39000	select from the alternatives.     Figure 5  shows  an  experimentally
39100	obtained computer description of a doll [3].
39200	
39300				INDUSTRIAL APPLICATIONS
39400	
39500	Recently,  several  laboratories  have begun to apply techniques from
39600	perception research to  practical  industrial  tasks.        Stanford
39700	University  has  demonstrated simple assembly operations using vision
39800	and touch. General Motors laboratories has succeeded  in  mounting  a
39900	wheel  on  an axle. Stanford Research Institute and Hitachi Ltd. have
40000	each demonstrated systems that can distinguish sheet metal parts on a
40100	moving  conveyor  belt  and  determine  their  orientation  to enable
40200	manipulation.     Template-matching  techniques  were  used  to  take
40300	advantage of the two-dimensional nature of these tasks. Moreover, the
40400	conveyor demonstrations relied on the contrast between shiny metallic
40500	parts  and  the  black belt to simplify segmentation. Many industrial
40600	processes share similar constraints or can be readily  redesigned  to
40700	do  so.  We thus expect a proliferation of industrial applications of
40800	computer perception in the near future.